package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.utils.ParseUtils;

import java.util.List;

//你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，
// 这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的
//房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
// 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
//
// 示例 1：
//输入：nums = [2,3,2]
//输出：3
//解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
//
// 示例 2：
//输入：nums = [1,2,3,1]
//输出：4
//解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
//     偷窃到的最高金额 = 1 + 3 = 4 。
//
// 示例 3：
//输入：nums = [1,2,3]
//输出：3
//
// 提示：
// 1 <= nums.length <= 100
// 0 <= nums[i] <= 1000
// Related Topics 数组 动态规划


public class Solution213 {
	// 正解，分成两个198
	// f(i) = f(i-2) + n[i]
	// g(i,j) = f(i - 2, j - 2) + n[i] + n[j] &&j-i>2 && (j == len && i!=0)
	public int rob(int[] nums) {
		if (nums.length == 0) return 0;
		if (nums.length == 1) return nums[0];
		int max0 = nums[0];
		int max1 = Math.max(nums[0], nums[1]);

		int temp = 0;
		for (int i = 2; i < nums.length; i++) {
			temp = max1;
			max1 = Math.max(max0 + nums[i], max1);
			max0 = temp;
		}
		return Math.max(max0, max1);
	}

	public static void main(String[] args) {
		Solution213 solution = new Solution213();
		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
//		System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
		System.out.println(solution.rob(new int[]{1, 3, 1, 3, 100}));
	}

}
